package com.jwetherell.my.problems.dynamicprogramming;

/**
 * http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-
 * subsequence/
 * 
 * The longest Increasing Subsequence (LIS) problem is to find the length of the
 * longest subsequence of a given sequence such that all elements of the
 * subsequence are sorted in increasing order. For example, length of LIS for {
 * 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}.
 * 
 * Note: A subsequence is a sequence that appears in the same relative order,
 * but not necessarily contiguous.
 * 
 * @author yatendra
 * 
 */
public class LIS_Longest_Increasing_Subsequence {

	private int[] data;
	private int maxLISLength = 1;

	public static void main(String[] args) {
		LIS_Longest_Increasing_Subsequence lisProblem = new LIS_Longest_Increasing_Subsequence();

		lisProblem.data = new int[] { 10, 22, 9, 33, 21, 50, 41, 60, 80 };
		lisProblem.printData();

		// Few variable initializations for recording running-time
		String TIME_STR_PREFIX = " [Time: ";
		String TIME_STR_SUFFIX = " nanoseconds]";
		int divisor = 1;
		long startTime;
		long totalTime;
		
		// Recursive solution
		startTime = System.nanoTime();
		lisProblem.findLIS_Recursively(lisProblem.data.length - 1);
		totalTime = (System.nanoTime() - startTime) / divisor;
		System.out.println("LIS (using Recursion): " + lisProblem.maxLISLength + TIME_STR_PREFIX + totalTime + TIME_STR_SUFFIX);

		// DP - Memoization
		startTime = System.nanoTime();
		lisProblem.maxLISLength = 1;
		lisProblem.dpLookupArray = new int[lisProblem.data.length];
		lisProblem.initDPLookupArray();
		lisProblem.findLIS_Memoization(lisProblem.data.length - 1);
		totalTime = (System.nanoTime() - startTime) / divisor;
		System.out.println("LIS (using DP-Memoization): " + lisProblem.maxLISLength + TIME_STR_PREFIX + totalTime + TIME_STR_SUFFIX);

		// DP - Tabulization
		startTime = System.nanoTime();
		lisProblem.maxLISLength = 1;
		int LIS = lisProblem.findLIS_Tabulization(lisProblem.data.length);
		totalTime = (System.nanoTime() - startTime) / divisor;
		System.out.println("LIS (using DP-Tabulization): " + LIS + TIME_STR_PREFIX + totalTime + TIME_STR_SUFFIX);

	}

	/*
	 * DP - Tabulization (Bottom Up)
	 */
	private int findLIS_Tabulization(int n) {

		int[] dpLookupArray = new int[n]; // DP lookup table

		dpLookupArray[0] = 1; // base-case in corresponding recursive solution

		for (int i = 1; i < n; i++) // start loop after the base-cases to calculate results for rest of the cases till case 'n'
			for (int j = 0; j < i; j++)
				if (data[j] < data[i] && dpLookupArray[j]+1 > dpLookupArray[i])
					dpLookupArray[i] = dpLookupArray[j]+1;

		/* Pick maximum of all LIS values */
		int max = 0;
		for (int i = 0; i < n; i++)
			if (max < dpLookupArray[i])
				max = dpLookupArray[i];

		return max;
	}


	
	
	
	/*
	 * DP - Memoization (Top Down)
	 */
	private static final int DP_LOOK_UP_ARRAY_NIL_VALUE = -1;
	private int[] dpLookupArray;

	private void initDPLookupArray() {
		for (int i = 0; i < dpLookupArray.length; i++)
			dpLookupArray[i] = DP_LOOK_UP_ARRAY_NIL_VALUE;
	}

	private int findLIS_Memoization(int tillIndex) {

		if (dpLookupArray[tillIndex] == DP_LOOK_UP_ARRAY_NIL_VALUE) {
			if (tillIndex == 0)
				dpLookupArray[tillIndex] = 1;

			int res;
			int max_ending_here = 1; // length of LIS ending with arr[n-1]

			/*
			 * Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2].
			 * If arr[i-1] is smaller than arr[n-1], and max ending with
			 * arr[n-1] needs to be updated, then update it
			 */
			for (int i = 0; i < tillIndex; i++) {
				res = findLIS_Recursively(i);
				if (data[i] < data[tillIndex] && (res + 1 > max_ending_here))
					max_ending_here = res + 1;
			}

			// Compare max_ending_here with the overall max. And update the
			// overall max if needed
			if (maxLISLength < max_ending_here)
				maxLISLength = max_ending_here;

			// Return length of LIS ending with arr[n-1]
			dpLookupArray[tillIndex] = max_ending_here;
		}
		return dpLookupArray[tillIndex];
	}

	// Recursive solution
	private int findLIS_Recursively(int tillIndex) {

		if (tillIndex == 0)
			return 1;

		int res;
		int max_ending_here = 1; // length of LIS ending with arr[n-1]

		/*
		 * Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If
		 * arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs
		 * to be updated, then update it
		 */
		for (int i = 0; i < tillIndex; i++) {
			res = findLIS_Recursively(i);
			if (data[i] < data[tillIndex] && (res + 1 > max_ending_here))
				max_ending_here = res + 1;
		}

		// Compare max_ending_here with the overall max. And update the
		// overall max if needed
		if (maxLISLength < max_ending_here)
			maxLISLength = max_ending_here;

		// Return length of LIS ending with arr[n-1]
		return max_ending_here;
	}

	private void printData() {
		System.out.print("Input: ");
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
		System.out.println();
	}
}